{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Beautiful Substrings II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #string #number-theory #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #字符串 #数论 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: beautifulSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计美丽子字符串 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和一个正整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>用 <code>vowels</code> 和 <code>consonants</code> 分别表示字符串中元音字母和辅音字母的数量。</p>\n",
    "\n",
    "<p>如果某个字符串满足以下条件，则称其为 <strong>美丽字符串</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>vowels == consonants</code>，即元音字母和辅音字母的数量相等。</li>\n",
    "\t<li><code>(vowels * consonants) % k == 0</code>，即元音字母和辅音字母的数量的乘积能被 <code>k</code> 整除。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回字符串 <code>s</code> 中 <strong>非空美丽子字符串</strong> 的数量。</p>\n",
    "\n",
    "<p>子字符串是字符串中的一个连续字符序列。</p>\n",
    "\n",
    "<p>英语中的<strong> 元音字母 </strong>为 <code>'a'</code>、<code>'e'</code>、<code>'i'</code>、<code>'o'</code> 和 <code>'u'</code> 。</p>\n",
    "\n",
    "<p>英语中的<strong> 辅音字母 </strong>为除了元音字母之外的所有字母。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"baeyh\", k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>字符串 s 中有 2 个美丽子字符串。\n",
    "- 子字符串 \"b<em><strong>aeyh</strong></em>\"，vowels = 2（[\"a\",\"e\"]），consonants = 2（[\"y\",\"h\"]）。\n",
    "可以看出字符串 \"aeyh\" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。\n",
    "- 子字符串 \"<em><strong>baey</strong></em>h\"，vowels = 2（[\"a\",\"e\"]），consonants = 2（[\"b\",\"y\"]）。\n",
    "可以看出字符串 \"baey\" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。\n",
    "可以证明字符串 s 中只有 2 个美丽子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abba\", k = 1\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>字符串 s 中有 3 个美丽子字符串。\n",
    "- 子字符串 \"<strong><em>ab</em></strong>ba\"，vowels = 1（[\"a\"]），consonants = 1（[\"b\"]）。\n",
    "- 子字符串 \"ab<strong><em>ba</em></strong>\"，vowels = 1（[\"a\"]），consonants = 1（[\"b\"]）。\n",
    "- 子字符串 \"<em><strong>abba</strong></em>\"，vowels = 2（[\"a\",\"a\"]），consonants = 2（[\"b\",\"b\"]）。\n",
    "可以证明字符串 s 中只有 3 个美丽子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"bcdf\", k = 1\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>字符串 s 中没有美丽子字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-beautiful-substrings-ii](https://leetcode.cn/problems/count-beautiful-substrings-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-beautiful-substrings-ii](https://leetcode.cn/problems/count-beautiful-substrings-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"baeyh\"\\n2', '\"abba\"\\n1', '\"bcdf\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, a: str, k: int) -> int:\n",
    "        for d in count(1):\n",
    "            if d*d%(4*k) == 0:\n",
    "                k = d \n",
    "                break\n",
    "        s = list(accumulate([1 if c in \"aeiou\" else -1 for c in a], initial=0))\n",
    "        cnt = Counter()\n",
    "        ans=0\n",
    "        for i,x in enumerate(s):\n",
    "            p = (i%k,x)\n",
    "            ans += cnt[p]\n",
    "            cnt[p] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        n= len(s)\n",
    "        # 分解k\n",
    "        ps = []\n",
    "        isnp = [0]*1001\n",
    "        for x in range(2, 1001):\n",
    "            if not isnp[x]:\n",
    "                ps.append(x)\n",
    "            for p in ps:\n",
    "                if p* x > 1000:\n",
    "                    break\n",
    "                isnp [p *x]=1\n",
    "                if x%p==0:\n",
    "                    break\n",
    "        x = k\n",
    "        y = 1\n",
    "        for p in ps:\n",
    "            if x%p ==0:\n",
    "                w = 0\n",
    "                while x%p==0:\n",
    "                    x//=p\n",
    "                    w+=1\n",
    "                y *= p**((w+1)//2)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        d = {}\n",
    "        d[0] = [0]*y\n",
    "        d[0][0]  = 1\n",
    "        vs = cs = 0\n",
    "        ans = 0\n",
    "        for i , c in enumerate(s):\n",
    "            if c in ['a', 'e', 'i', 'o','u']:vs +=1\n",
    "            else: cs+=1\n",
    "            diff = cs - vs\n",
    "            if diff not in d:\n",
    "                d[diff] = [0]*y\n",
    "            ans += d[diff][cs%y]\n",
    "            d[diff][cs%y]+=1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        \n",
    "        vowels = {'a', 'e', 'i', 'o', 'u'}\n",
    "        n = len(s)\n",
    "\n",
    "        offset = 0\n",
    "        # 最小的基数x, 是的x^2 % k = 0,\n",
    "        # offset需要乘以2， 因为它是x+x\n",
    "        for i in range(1, k+1):\n",
    "            if (i * i) % k == 0:\n",
    "                offset = i * 2\n",
    "                break\n",
    "        \n",
    "        res = 0\n",
    "        prefix = {0:{0: 1}}   # 前缀和为0的情况，里面的字典表示对offset取模的个数\n",
    "        pre = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] in vowels:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre -= 1\n",
    "            key = (i + 1) % offset\n",
    "            if pre in prefix:\n",
    "                temp = prefix[pre]       # 前缀和为pre的情况\n",
    "                res += temp.get(key, 0)  # 长度为key的情况\n",
    "            prefix.setdefault(pre, {}).update({key:prefix.get(pre, {}).get(key, 0) + 1})\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.n = n\n",
    "        self.primes = []\n",
    "        self.min_div = [0] * (n + 1)\n",
    "        self.min_div[1] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "\n",
    "            for p in self.primes:\n",
    "                if i * p > n:\n",
    "                    break\n",
    "                self.min_div[i * p] = p\n",
    "                if i % p == 0:\n",
    "                    break\n",
    "\n",
    "    def prime_factorization(self, x: int):\n",
    "        while 1 < x <= self.n:\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0:\n",
    "                cnt += 1\n",
    "                x //= p\n",
    "            yield p, cnt\n",
    "\n",
    "pt = PrimeTable(1001)\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        se = {'a', 'e', 'i', 'o', 'u'}\n",
    "        lst = []\n",
    "        for p, cnt in pt.prime_factorization(k):\n",
    "            if cnt % 2 == 1:\n",
    "                lst.append([p, cnt + 1])\n",
    "            else:\n",
    "                lst.append([p, cnt])\n",
    "        val = 1\n",
    "        for p, cnt in lst:\n",
    "            val = val * (p ** (cnt // 2))\n",
    "        cnt1 = cnt2 = 0\n",
    "        d = defaultdict(dict)\n",
    "        d[0][0] = 1\n",
    "        ans = 0\n",
    "        for letter in s:\n",
    "            if letter in se:\n",
    "                cnt1 += 1\n",
    "            else:\n",
    "                cnt2 += 1\n",
    "            delta = cnt1 - cnt2\n",
    "            pre = d[delta]\n",
    "            temp = cnt1 % val\n",
    "            if temp in pre:\n",
    "                ans += pre[temp]\n",
    "                pre[temp] += 1\n",
    "            else:\n",
    "                pre[temp] = 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        # 对k进行变换 8 -> 4\n",
    "        # if sqrt(k) == int(sqrt(k)): k = int(sqrt(k))    # k <- sqrt(k) 不对!\n",
    "        bases = Counter()\n",
    "        for x in range(2, ceil(sqrt(k+1))):\n",
    "            while k%x == 0:\n",
    "                bases[x] += 1\n",
    "                k //= x\n",
    "        if k != 1: bases[k] += 1\n",
    "        k = 1\n",
    "        for x,c in bases.items():\n",
    "            k *= x**(ceil(c/2))\n",
    "        step = 2*k              # 最小长度\n",
    "        vowels = 'aeiou'\n",
    "        s = [1 if x in vowels else -1 for x in s]\n",
    "        csum = 0\n",
    "        csum2d = defaultdict(Counter)\n",
    "        csum2d[0][step-1] = 1\n",
    "        ans = 0\n",
    "        for i,x in enumerate(s):\n",
    "            csum += x\n",
    "            # 匹配条件为: ccum相同, 同时idx相差2k的倍数\n",
    "            ans += csum2d[csum][i%step]\n",
    "            csum2d[csum][i%step] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "vowels = set('aeiou')\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        p = next(i for i in count(1) if i**2 % k == 0) * 2\n",
    "        visited = [Counter() for _ in range(p)]\n",
    "        visited[-1][0] = 1\n",
    "        res = v = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            v += 1 if s[i] in vowels else -1\n",
    "            res += visited[i % p][v]\n",
    "            visited[i % p][v] += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        \n",
    "        # minLength = 2\n",
    "        # for i in range(1, k + 1):\n",
    "        #     if (i ** 2) % k == 0:\n",
    "        #         minLength = i * 2\n",
    "        #         break\n",
    "\n",
    "        # 分解 k 得到 minLength\n",
    "        minLength = 2\n",
    "        for prime, dPrime in [[2, 4], [3, 9], [5, 25], [7, 49], [11, 121], [13, 169], [17, 289], [19, 361], [23, 529], [29, 841], [31, 961]]:\n",
    "            if dPrime > k: break\n",
    "            while k % dPrime == 0:\n",
    "                minLength *= prime\n",
    "                k //= dPrime\n",
    "        minLength *= k\n",
    "\n",
    "        # print(int(True),int(False))\n",
    "\n",
    "        dic = [defaultdict(int) for _ in range(minLength)]\n",
    "        dic[minLength - 1][0] += 1\n",
    "\n",
    "        ans = diff = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch in \"aeiou\": diff += 1\n",
    "            else: diff -= 1\n",
    "            dic[i % minLength][diff] += 1\n",
    "\n",
    "        for item in dic:\n",
    "            for num in item.values():\n",
    "                ans += num * (num - 1) // 2\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        nums = [1 if c in [\"a\", \"e\", \"i\", \"o\", \"u\"] else -1 for c in s]\n",
    "        ok = 0  # 允许的长度集合\n",
    "        for v in range(1, n // 2 + 1):\n",
    "            if (v * v) % k == 0:\n",
    "                ok |= 1 << (2 * v)\n",
    "\n",
    "        res = 0\n",
    "        preSum, curSum = defaultdict(int), 0\n",
    "        preSum[0] = 1 << n\n",
    "        for i, v in enumerate(nums, start=1):\n",
    "            curSum += v\n",
    "            prePos = preSum[curSum]\n",
    "            intersection = ok & (prePos >> (n - i))\n",
    "            res += intersection.bit_count()\n",
    "            preSum[curSum] |= 1 << (n - i)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        mod = 2\n",
    "        for i in range(int(sqrt(k)),1001):\n",
    "            if i*i %k==0:\n",
    "                mod = i*2\n",
    "                break\n",
    "        pre_cnt = [ [ ] for _ in range(mod) ]\n",
    "        pre_cnt[-1].append(0)\n",
    "        cur = 0\n",
    "        for i,c in enumerate(s): \n",
    "            cur += 1 if c in 'aeiou' else -1 \n",
    "            pre_cnt[i%mod] .append(  cur ) \n",
    "        ans = 0\n",
    "        for pre in pre_cnt:\n",
    "            ans += sum( v*(v-1)//2 for v in Counter(pre).values() )\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        s = 'a'+s\n",
    "\n",
    "        sn=[]\n",
    "        for i in range(len(s)):\n",
    "            tmp = 0 if i == 0 else sn[-1]\n",
    "            if s[i] in 'aeiou':\n",
    "                sn.append(tmp+1)\n",
    "            else:\n",
    "                sn.append(tmp-1)\n",
    "\n",
    "        dd = {}\n",
    "        k_ = 4*k\n",
    "        for i in range(2, k_):\n",
    "            while k_%i == 0:\n",
    "                k_ = int(k_/i)\n",
    "                dd.setdefault(i, 0)\n",
    "                dd[i] += 1\n",
    "        dd[k_]=1\n",
    "\n",
    "        k_ = 1\n",
    "        for k,v in dd.items():\n",
    "            if v%2 == 0:\n",
    "                k_ *= k**(v/2)\n",
    "            else:\n",
    "                k_ *= k**(int(v/2)+1)\n",
    "        h = {}\n",
    "        for i in range(len(s)):\n",
    "            tmp = int(i%k_)\n",
    "            h.setdefault(tmp, {})\n",
    "            h[tmp].setdefault(sn[i], 0)\n",
    "            h[tmp][sn[i]] += 1\n",
    "            if s[i] == 'h':\n",
    "                print(tmp, sn[i])\n",
    "            if tmp==1 and sn[i]==0:\n",
    "                print(s[i])\n",
    "        \n",
    "        ret = 0\n",
    "        for k1, v1 in h.items():\n",
    "            for k2, v2 in v1.items():\n",
    "                ret += int((v2*(v2-1)/2))\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        for d in count(1):\n",
    "            if (d * d) % (4 * k) == 0:\n",
    "                k = d\n",
    "                break\n",
    "        # print(k)\n",
    "        ls = []\n",
    "        for c in s:\n",
    "            if c in \"aeiou\":\n",
    "                ls.append(1)\n",
    "            else:\n",
    "                ls.append(-1)\n",
    "        sm = list(accumulate(ls, initial = 0))\n",
    "        # print(sm)\n",
    "        cnt = [Counter() for _ in range(k)]\n",
    "        ans = 0\n",
    "        for i, x in enumerate(sm):\n",
    "            ans += cnt[i % k][x]\n",
    "            cnt[i % k][x] += 1\n",
    "            # print(cnt, i, x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        s = 'a'+s\n",
    "\n",
    "        sn=[]\n",
    "        for i in range(len(s)):\n",
    "            tmp = 0 if i == 0 else sn[-1]\n",
    "            if s[i] in 'aeiou':\n",
    "                sn.append(tmp+1)\n",
    "            else:\n",
    "                sn.append(tmp-1)\n",
    "\n",
    "        dd = {}\n",
    "        k_ = 4*k\n",
    "        for i in range(2, k_):\n",
    "            while k_%i == 0:\n",
    "                k_ = int(k_/i)\n",
    "                dd.setdefault(i, 0)\n",
    "                dd[i] += 1\n",
    "        dd[k_]=1\n",
    "\n",
    "        k_ = 1\n",
    "        for k,v in dd.items():\n",
    "            if v%2 == 0:\n",
    "                k_ *= k**(v/2)\n",
    "            else:\n",
    "                k_ *= k**(int(v/2)+1)\n",
    "        print(dd)\n",
    "        print(k_)\n",
    "        h = {}\n",
    "        for i in range(len(s)):\n",
    "            tmp = int(i%k_)\n",
    "            h.setdefault(tmp, {})\n",
    "            h[tmp].setdefault(sn[i], 0)\n",
    "            h[tmp][sn[i]] += 1\n",
    "            if s[i] == 'h':\n",
    "                print(tmp, sn[i])\n",
    "            if tmp==1 and sn[i]==0:\n",
    "                print(s[i])\n",
    "        \n",
    "        ret = 0\n",
    "        print(h)\n",
    "        for k1, v1 in h.items():\n",
    "            for k2, v2 in v1.items():\n",
    "                ret += int((v2*(v2-1)/2))\n",
    "                # tmp = 1\n",
    "                # for i in range(2, v2+1):\n",
    "                #     tmp *= i\n",
    "                # ret += int(tmp/2)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        k = self.sqrt(k * 4)\n",
    "        cnt = Counter([(0, 0)])  # k-1 和 -1 同余\n",
    "        ans = pre_sum = 0\n",
    "        for i, c in enumerate(s):\n",
    "            pre_sum += 1 if c in \"aeiou\" else -1\n",
    "            p = ((i + 1) % k, pre_sum)\n",
    "            ans += cnt[p]\n",
    "            cnt[p] += 1\n",
    "        return ans\n",
    "\n",
    "    def sqrt(self, n: int) -> int:\n",
    "        res = 1\n",
    "        i = 2\n",
    "        while i * i <= n:\n",
    "            i2 = i * i\n",
    "            while n % i2 == 0:\n",
    "                res *= i\n",
    "                n //= i2\n",
    "            if n % i == 0:\n",
    "                res *= i\n",
    "                n //= i\n",
    "            i += 1\n",
    "        if n > 1:\n",
    "            res *= n\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        k = self.sqrt(k * 4)\n",
    "        cnt = Counter([(k - 1, 0)])  # k-1 和 -1 同余\n",
    "        ans = pre_sum = 0\n",
    "        for i, c in enumerate(s):\n",
    "            pre_sum += 1 if c in \"aeiou\" else -1\n",
    "            p = (i % k, pre_sum)\n",
    "            ans += cnt[p]\n",
    "            cnt[p] += 1\n",
    "        return ans\n",
    "\n",
    "    def sqrt(self, n: int) -> int:\n",
    "        res = 1\n",
    "        i = 2\n",
    "        while i * i <= n:\n",
    "            i2 = i * i\n",
    "            while n % i2 == 0:\n",
    "                res *= i\n",
    "                n //= i2\n",
    "            if n % i == 0:\n",
    "                res *= i\n",
    "                n //= i\n",
    "            i += 1\n",
    "        if n > 1:\n",
    "            res *= n\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        ans = key = vonum = 0\n",
    "        pre = [0 for _ in range(n+1)]\n",
    "        tupdict = {}\n",
    "        tupdict[(0,0)] = 1\n",
    "\n",
    "        k2 = 2\n",
    "        for i in range(2, 6*10**4):\n",
    "            if i > k:\n",
    "                break\n",
    "            cnt = 0\n",
    "            i2 = i*i\n",
    "            while k % i2 == 0:\n",
    "                cnt += 1\n",
    "                k /= i2\n",
    "                k2 *= i\n",
    "            if k % i == 0:\n",
    "                k2 *= i\n",
    "                k //= i\n",
    "                \n",
    "\n",
    "        #print(k2)\n",
    "\n",
    "        voset = set(['a','e','i', 'o','u'])\n",
    "        for i in range(n):\n",
    "            if s[i] in voset:\n",
    "                key += 1\n",
    "            else:\n",
    "                key -= 1\n",
    "            key1 = (i+1)%k2\n",
    "            if (key1, key) in tupdict:\n",
    "                ans += tupdict[(key1, key)]\n",
    "            if (key1, key) not in tupdict:\n",
    "                tupdict[(key1, key)] = 0\n",
    "            tupdict[(key1, key)] += 1\n",
    "            #print(s[i], (i+1)%k2, key, tupdict, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        # vowels = consonants == l / 2\n",
    "        # (l / 2) * (l / 2) % k == 0\n",
    "        # (l * l) % (4 * k) == 0\n",
    "        k *= 4\n",
    "        for l in count(1):\n",
    "            if (l * l) % k == 0:\n",
    "                k = l\n",
    "                break\n",
    "        \n",
    "        n = len(s)\n",
    "        f = [0] * (n+1)\n",
    "        for i, v in enumerate(s):\n",
    "            f[i+1] = f[i] + (1 if v in \"aeiou\" else -1)\n",
    "        \n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        # print(f)\n",
    "        for i, v in enumerate(f):\n",
    "            ans += cnt[(i%k, v)]\n",
    "            # print(cnt, ans)\n",
    "            cnt[(i%k, v)] += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        for i in count(1):\n",
    "            if (i * i) % (4 * k) == 0:\n",
    "                k = i\n",
    "                break\n",
    "        \n",
    "        n = len(s)\n",
    "        f = [0] * (n+1)\n",
    "        for i, v in enumerate(s):\n",
    "            f[i+1] = f[i] + (1 if v in \"aeiou\" else -1)\n",
    "        \n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        # print(f)\n",
    "        for i, v in enumerate(f):\n",
    "            ans += cnt[(i%k, v)]\n",
    "            # print(cnt, ans)\n",
    "            cnt[(i%k, v)] += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        a = [1 if ch in \"aeiou\" else -1 for ch in s]\n",
    "        pf = [0] * (n + 1)\n",
    "        pf[1] = a[0]\n",
    "        for i in range(1,n):\n",
    "            pf[i + 1] = pf[i] + a[i]\n",
    "        for d in count(1):\n",
    "            if d * d % (4 * k) == 0:\n",
    "                k = d\n",
    "                break\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for i,x in enumerate(pf):\n",
    "            p = (i % k,x)\n",
    "            ans += cnt[p]\n",
    "            cnt[p] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        d=1\n",
    "        while True:\n",
    "            if (d*d)%(4*k)==0:\n",
    "                k=d\n",
    "                break\n",
    "            d+=1\n",
    "        nums=[]\n",
    "        for w in s:\n",
    "            if w in 'aeiou':\n",
    "                nums.append(1)\n",
    "            else:\n",
    "                nums.append(-1)\n",
    "        presum=list(accumulate(nums,initial=0))\n",
    "\n",
    "        d=defaultdict(int)\n",
    "        res=0\n",
    "        for i,pre in enumerate(presum):\n",
    "            res+=d[(pre,i%k)]\n",
    "            d[(pre,i%k)]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        for d in count(1):\n",
    "            if d*d % (4*k) == 0:\n",
    "                k = d\n",
    "                break\n",
    "        n = len(s)\n",
    "        presum = [0]*(n+1)\n",
    "        cnt = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            if s[i] in ['a', 'e', 'i', 'o', 'u']:\n",
    "                presum[i+1] = presum[i] + 1\n",
    "                cnt[i+1] = cnt[i] + 1\n",
    "            else:\n",
    "                presum[i+1] = presum[i] - 1\n",
    "                cnt[i+1] = cnt[i]\n",
    "        tmp = dict()\n",
    "        res = 0\n",
    "        for i in range(n+1):\n",
    "            if (i%k, presum[i]) not in tmp:\n",
    "                tmp.update({(i%k, presum[i]):1})\n",
    "            else:\n",
    "                res += tmp[(i%k, presum[i])]\n",
    "                tmp[(i%k, presum[i])] += 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        for d in count(1):\n",
    "            if d*d % (4*k) == 0:\n",
    "                k = d\n",
    "                break\n",
    "        n = len(s)\n",
    "        presum = [0]*(n+1)\n",
    "        cnt = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            if s[i] in ['a', 'e', 'i', 'o', 'u']:\n",
    "                presum[i+1] = presum[i] + 1\n",
    "                cnt[i+1] = cnt[i] + 1\n",
    "            else:\n",
    "                presum[i+1] = presum[i] - 1\n",
    "                cnt[i+1] = cnt[i]\n",
    "        tmp = dict()\n",
    "        res = 0\n",
    "        for i in range(n+1):\n",
    "            if (i%k, presum[i]) not in tmp:\n",
    "                tmp.update({(i%k, presum[i]):1})\n",
    "            else:\n",
    "                res += tmp[(i%k, presum[i])]\n",
    "                tmp[(i%k, presum[i])] += 1\n",
    "        return res\n",
    "        # for i in range(n+1):\n",
    "        #     if presum[i] not in tmp:\n",
    "        #         tmp.update({presum[i]:[i]}) # 存的是索引，方便去找对应的cnt[i]\n",
    "        #     else:\n",
    "        #         for j in tmp[presum[i]]:\n",
    "        #             if cnt[i]-cnt[j] and ((cnt[i]-cnt[j])**2)%k == 0:\n",
    "        #                 res += 1\n",
    "        #         tmp[presum[i]].append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        wSet = set()\n",
    "        aSet = ['a', 'e', 'i', 'o', 'u']\n",
    "        for i in range(k):\n",
    "            if (i*i)%k == 0:\n",
    "                wSet.add(i)\n",
    "        record = {}\n",
    "        record[\"0\"+\"#\"+\"0\"] = 1\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in aSet:\n",
    "                cnt1+=1\n",
    "            else:\n",
    "                cnt2+=1\n",
    "            delta = cnt1 - cnt2\n",
    "            for w in wSet:\n",
    "                if str(delta)+\"#\"+str((cnt1 - w + k)%k) in record:\n",
    "                    res += record[str(delta)+\"#\"+str((cnt1 - w + k)%k)]\n",
    "            \n",
    "            record[str(delta)+\"#\"+str(cnt1%k)] = record.get(str(delta)+\"#\"+str(cnt1%k), 0) + 1\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubstrings(self, s: str, k: int) -> int:\n",
    "        subk=[]\n",
    "        for i in range(1,k+1):\n",
    "            if (i**2)%k==0:\n",
    "                subk.append(i)\n",
    "        n=len(s)\n",
    "        yuanls=['i','o','e','u','a']\n",
    "        dpls=[[0,0] for i in range(n+1)]\n",
    "        dic={}\n",
    "        dic[0]=[0]\n",
    "        for i in range(n):\n",
    "            if s[i] in yuanls:\n",
    "                dpls[i][0]=dpls[i-1][0]+1\n",
    "                dpls[i][1]=dpls[i-1][1]\n",
    "            else:\n",
    "                dpls[i][0] = dpls[i - 1][0]\n",
    "                dpls[i][1] = dpls[i - 1][1]+1\n",
    "            if dpls[i][0]-dpls[i][1] not in dic:\n",
    "                dic[dpls[i][0]-dpls[i][1]]=[dpls[i][0]]\n",
    "            else:\n",
    "                dic[dpls[i][0]-dpls[i][1]].append(dpls[i][0])\n",
    "        #print(dpls)\n",
    "        #print(dic)\n",
    "        r=0\n",
    "        for nums in dic.values():\n",
    "            newdic={}\n",
    "            for i in range(len(nums)):\n",
    "                for jbk in subk:\n",
    "                    if (nums[i]-jbk)%k in newdic:\n",
    "                        r+=newdic[(nums[i]-jbk)%k]\n",
    "                if (nums[i]%k) in newdic:\n",
    "                    newdic[nums[i]%k]+=1\n",
    "                else:\n",
    "                    newdic[nums[i]%k]=1\n",
    "        return r"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
